A Randomized Greedy Algorithm for Near-Optimal Sensor Scheduling in Large-Scale Sensor Networks

摘要

We study the problem of scheduling sensors in a resource-constrained lineardynamical system, where the objective is to select a small subset of sensorsfrom a large network to perform the state estimation task. We formulate thisproblem as the maximization of a monotone set function under a matroidconstraint. We propose a randomized greedy algorithm that is significantlyfaster than state-of-the-art methods. By introducing the notion of curvaturewhich quantifies how close a function is to being submodular, we analyze theperformance of the proposed algorithm and find a bound on the expected meansquare error (MSE) of the estimator that uses the selected sensors in terms ofthe optimal MSE. Moreover, we derive a probabilistic bound on the curvature forthe scenario where{\color{black}{ the measurements are i.i.d. random vectorswith bounded $\ell_2$ norm.}} Simulation results demonstrate efficacy of therandomized greedy algorithm in a comparison with greedy and semidefiniteprogramming relaxation methods.